package com.exercises;

import java.util.HashMap;

/**
 * 两数之和
 *
 * @author: zhangzy
 * @date: 2022/3/23
 * @desc:
 */
public class SumTwoNumbers {
    static int loopCount = 0; // 用于记录循环次数
    public static void main(String[] args) {
        SumTwoNumbers sumTwoNumbers = new SumTwoNumbers();
        int[] ints = sumTwoNumbers.method2(new int[]{2, 5, 4, 8, 9, 7}, 9);
        System.out.println(ints[0] + " " + ints[1]);
        System.out.println("循环次数" + loopCount);
    }
    /**
     * 题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     * 示例 1：
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     */

    /**
     * 方法一：暴力枚举
     *
     * @return 思路及算法:最容易想到的方法是枚举数组中的每一个数x，寻找数组中是否存在 target - x。
     * 我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。
     * 而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
     * 复杂度分析
     * <p>
     * 时间复杂度：O(N2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] method1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) { // 外层循环
            for (int j = i + 1; j < nums.length; j++) { // 内层循环
                if (nums[i] + nums[j] == target) { // 相邻2个数比较
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    // 哈希表
    public int[] method2(int[] nums, int target) {
        // 创建一个Hash表
        HashMap<Integer, Integer> integerIntegerHashMap = new HashMap<>();

        // 遍历数组将数据存入Hash表中
        for (int i = 0; i < nums.length; i++) {
            // 目标值- 当前遍历的值,判断integerIntegerHashMap是否含有target的键
            if (integerIntegerHashMap.containsKey(target - nums[i])) {
                return new int[]{integerIntegerHashMap.get(target - nums[i]), i};
            }
            // 存入hashMap 1（4,0）2(2,1)
            integerIntegerHashMap.put(nums[i], i);
            loopCount++; // 每次循环增加计数器
        }
        return new int[0];
    }

}
